NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## WHAT IS IT?

Put shortly, this is a model of the traveling salesman problem using a genetic algorithm. Below is an in deph description of both components.

##
THE TRAVELING SALESMAN PROBLEM

The Traveling Salesman Problem (TSP) is a famous optimization problem, studied extensively in mathematics and computer science (Yuping). A salesman must visit a network of cities once and return to the starting city. The problem is to find the shortest tour among these cities to minimize the total travel distance and cost of the tour (Kashyap).

One way of solving the TSP is to list all of the possible solutions and evaluate them one-by-one. This works well for smaller amounts of cities, but will become more time consuming as more cities are added, for the number of solutions to the TSP is represented by the formula: (N-1!). For this reason, emphasis has shifted from finding the best solution to finding good solutions in reasonable amounts of time. The genetic algorithm is one of the best algorithms for finding good solutions quickly (Ahmed).
The TSP has attracted the attention of many people and will remain as an active research area. The main reason for this is large numbers of real-world problems can be modeled by the TSP, for example the automated drilling of printed circuit boards is one of them. By finding an efficient way to solve the TSP, other similar problems can be solved as well (Ahmed).

##
THE GENETIC ALGORITHM

Essentially, genetic algorithms are solution-searching techniques based on the survival of the fittest, crossover, and mutation processes of evolutionary biology. They have been used for solving a number of different complicated problems, including the TSP. The original theory, based on genetic structure and the behavior of chromosomes in nature, was developed by John Holland and his students in the early 1970s. A population of chromosomes, represented by encoded solutions, is changed by applying three main genetic operators to the algorithm in each generation: selection, crossover, and mutation. The fitness of the chromosomes (how well individual solutions satisfy set criteria) is measured via the fitness function. The algorithm proceeds to cycle through this process until an adequate solution is found. Each time chromosomes cycle through the algorithm, a new generation is created [2].

Similar to the way organisms adapt and improve, solutions produced through the algorithm should improve with every successive generation. Through this process, genetic algorithms are able to produce accurate solutions to complicated problems in reasonable amounts of time (Ahmed).

The main parts of the genetic algorithm include:
-Initial population and encoding
-The fitness function
-Selection
-Crossover
-Mutation

Each are explaned below

## HOW IT WORKS: STEPS BELOW:

##
INITIAL POPULATION

The initial population of chromosomes, necessary to start the algorithm, is randomly generated; each chromosome will represent a solution �a tour. To encode the tours, an appropriate encoding method needs to be selected [5]. Path representation is used to encode the tours; characters will represent cities. The number of characters in the path is equal to the number of cities in the tour and specific characters cannot repeat; for the salesman cannot visit one city more than once (Ahmed). The length of the tour, or the distance traveled by the salesman, is equivalent to the fitness of the tour and depends on the ordering of cities [2]. For example, the following figure represents a path the salesman could take on the tour:

## FITNESS FUNCTION

The fitness function determines how �good� a chromosome is. In the case of the TSP, the fitness of a particular tour is equal to the distance traveled if the tour was taken. The shortest tours have the best fitness, making the TSP a minimization problem (Bryant). The model may be extended to include factors like air travel cost and the sales potential of each city. Each factor is weighted a certain amount contributes to the total fitness of the solution: similar to weighted grades. To do this the problem needs to be converted into a maximization problem.

Genetic algorithms are usually used in maximization problems. The algorithm will still function properly as a minimization problem, but for scientific accuracy it needs to be converted into a maximization problem. As described above, if other factors needed to be added in, it is easier to convert the distance traveled to a maximization problem rather than covering all of the other factors to minimization problems. The following equation will convert the problem:

1/ Total Distance Traveled

The total distance traveled can be calculated using the distance formula for each point in the tour (Bhattacharyya). Although this is the proper way to express the problem, it is easier to see how the algorithm works if left as a minimization problem (improvement is easily seen).

## SELECTION

The selection process is what determines the chromosomes will be selected for reproduction and the ones that will not. Generally, selection puts more emphasis on good solutions and eliminates bad solutions, while keeping a constant population size. Multiple copies of good solutions are made; each with varying characteristics, an most bad solutions are discarded. Some of the bad solutions are kept for the diversity among the solutions; adding a bad solution to the population helps to prevent convergence on one particular solution. (Kashyap).

Selection may be applied two main ways: roulette wheel selection and tournament selection. Both methods depend upon the fitness level of specific chromosomes in the population (Cunkas).

During roulette wheel selection, each chromosome is assigned a slot on an imaginary roulette wheel. The slot is proportionate to the fitness of the chromosomes; chromosomes with better fitness levels receive larger slots on the roulette wheel and therefore a larger probability of being selected. The roulette wheel is then spun a number of times and each solution the wheel lands on is put in a group. A parent chromosome is selected at random from the group to enter the crossover phase of the algorithm. This process is repeated again to produce another parent chromosome (Kashyap). Figure two shows a simple four-chromosome example of roulette wheel selection based on fitness level (higher percentages indicate higher fitness levels).

In tournament selection, selection is based on a tournament among a few chromosomes. Usually about two or three chromosomes are selected at random from the population, then the best of these chromosomes becomes a parent chromosome. This process is repeated again to produce another parent chromosome. The parent chromosomes then move on to the crossover phase of the algorithm (Cunkas). Figure three shows tournament selection between two sets of two chromosomes.

Essentially, both of these processes mimic Darwinian survival of the fittest in nature. In the natural world, selection is determined by an organism�s ability to survive. Organisms that are not fit enough to survive die out from climate changes, predators, and other obstacles, while others who are fit enough continue to reproduce, evolve, and become fitter. This is the main principle that drives the genetic algorithm (Ahmed).

This model uses tournament selection.

Essentially, both of these processes mimic Darwinian survival of the fittest in nature. In the natural world, selection is determined by an organism�s ability to survive. Organisms that are not fit enough to survive die out from climate changes, predators, and other obstacles, while others who are fit enough continue to reproduce, evolve, and become fitter. This is the main principle that drives the genetic algorithm (Ahmed).

## CROSSOVER

Crossover is the process by which two chromosomes combine tours to produce new offspring with characteristics from both tours. Two chromosomes are picked at random from a group of chromosomes and are combined to produce new ones (Kashyap). This process searches the solution space by maintaining common connections and by recombining uncommon genes (Cunkas).

The basic crossover method proceeds as follows. A common crossover site is selected randomly among the selected chromosomes and the information after the site is swapped. Figure four shows this crossover; called a single point crossover.

Unfortunately, this method of crossover is not supported by the TSP without extensive modification (Ahmed).

The single point method of crossover produces invalid offspring for the TSP; some cities in the tour will repeat. For this reason, the edge recombination crossover (ERX) has been developed. The ERX is not only compatible with the TSP; it emphasizes adjacency information instead of order and sequence. In other words, the ERX focuses on creating new chromosomes based on links into and out of cities in both parent�s tours. This creates better chromosomes by preserving similar genetic material between parent chromosomes. Additionally, the ERX is more likely to retain common links between the parents than other traditional methods (Kashap).

## MUTATION

The basic function of the mutation operator is to introduce diversity into the population of chromosomes (Potvin). Chromosomes are deliberately changed in random locations to increase diversity by exploring the entire solution space (Cunkas). Tours are randomly chosen to mutate based on some probability, then within the tours, random points are chosen for mutation (Bryant). This can be done a variety of ways: but for this algorithm two points within the picked tour are chosen, then changed randomly to other numbers. The tour is then checked to make sure it is still valid.
Swap mutation is another method of mutation. Just as the name suggests, a number of points in a chromosome are selected then swapped out. There is no need to check for validation of tours when using this method (Cunkas).
The process of mutation introduces random disturbances into the search process not possible through crossover. This allows for a wider search and a diverse population of solutions (Potvin).

## HOW TO USE IT

The population-size slider controls how large the initial population of solutions will be.

The tournament-size slider determines how large the tournament size will be in selection.

The mutation-rate slider controls how often each chromosome is mutated. The number shown is a percentage.

The number-of-cycles slider sets the number of cycles the algorithm will run before stopping.

The crossover-rate slider controls the percentages of solutions that are created from crossover to rather than cloning.

The preserve-common-links switch determines if the algorithm gives preference to common links among parents or not; for example, if both parents contain a link from city one to two, this link is more likely to be preserved with this option on.

The swap-mutation switch determines if the mutation method used. On: two point swap mutation. Off: two point random mutation

The best global fitness and best global solution monitors show the best solution the algorithm has found. If the algorithm �jumps� back up to a worse fitness, these monitors will keep the best fitness overall.

The fitness plot displays a graph of the worst, average, and best fitness for each cycle of the algorithm.

The map display shows the current map loaded into the algorithm, and when the algorithm has finished, draws out the best tour between the cities.

## THINGS TO NOTICE

-Notice how the fitness graph generally goes shows a lower fitness over time; this means the algorithm is 'learning' and producing better solutions.

-The algorithm will not find the best solution every time, but it usually finds a good one.

-When the model finishes running, it draws the shortest path it found on the map.

-A small population size usually generates better results than larger ones.

-The best fitnesses are around 280-290.

## THINGS TO TRY

-Try running the model more than once, you'll get different results most times.

-Move the crossover slider to 0, and observe the fitness graph.

-Move the mutation slider to 0, and observe the fitness graph.

-Turn the preserve-common-links? and swap-mutation? sliders off or on and run the model.

-Leave the model running overnight and observe the fitness when its finished.

## EXTENDING THE MODEL

-Use latitude and longitude for city locations.

-Change the crossover method.

-Change the selection method.

-Try a differant map.

-Include a tour cost equation (to calculate how much the tour would cost if taken) in the fitness evaluation process.

## RELATED MODELS

-Simple Genetic Algorithm

## CREDITS AND REFERENCES

-Ahmed, Zakir H. Genetic Algorithms for the Traveling Salesman Problem using Sequential Constructive Operator. Al-Imam.

-Al-Dulaimi, Buthainah Fahran and Hamza A. Ali. Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique. World Academy of Science, Engineering and Technology. 2008. Web. November 28, 2010. <citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.91>.

-Bhattacharyya, Malay, and Anup Kumar Bandyopadhyay. "COMPARATIVE STUDY OF SOME SOLUTION METHODS FOR TRAVELING SALESMAN PROBLEM USING GENETIC ALGORITHMS." Cybernetics & Systems 40.1 (2009): 1-24. Academic Search Premier. EBSCO. Web. 7 Dec. 2010.

-Bryant, Kylie. "Genetic Algorithms and the Traveling Salesman Problem." 2000. EBSCO. 6 12 2010.

-�unkas, Mehmet, and M. Yasin �zsa?lam. "A COMPARATIVE STUDY ON PARTICLE SWARM OPTIMIZATION AND GENETIC ALGORITHMS FOR TRAVELING SALESMAN PROBLEMS." Cybernetics & Systems 40.6 (2009): 490-507. Academic Search Premier. EBSCO. Web. 7 Dec. 2010.

-Jayalakshmi, G. Andal, S. Sathiamoorthy, and R. Rajaram. "A Hybrid Genetic Algorithm � A New Approach to Solve Traveling Salesman Problem." International Journal of Computational Engineering Science 2.2 (2001): 339. Academic Search Premier. EBSCO. Web. 7 Dec. 2010.

-Kashyap, Chhavi. "Genetic Algorithms." PowerPoint Presentation.

-Potvin, Jean-Yves. Genetic Algorithms for the Traveling Salesman Problem. Universite de Montreal. Allals of Operations Research. Web. November 30, 2010. < http://www.springerlink.com/content/j13214073h2808k0/>.

-Yuping, Wang, et al. "A new encoding based genetic algorithm for the traveling salesman problem." Engineering Optimization 38.1 (2006): 1-13. Academic Search Premier. EBSCO. Web. 7 Dec. 2010.

Also, take a look at wikipeadia's description of the genetic algorithm; its not half bad.